package linestructure

func InsertSort(arr []int) {
	N := len(arr)
	for i:=0; i<=N-1; i++ { // 指定范围 0-0 0-1 0-2 0-i 慢慢增大区间
		for j:=i; j>=0 ; j-- { // 在0-i区间内，从最后一个数开始与建一个数比较
			if j-1 >= 0 && arr[j] < arr[j-1] { // 如果前一个数比当前数大，交换位置，继续向前比较
				Swap(arr, j, j-1)
			} else { // 如果当前位置比之前的数大，则已经有序，退出循环
				break
			}
		}
	}
}

func InsertSort2(arr []int) {
	N := len(arr)
	for end:=0; end<=N-1; end++ { // 指定范围 0-0 0-1 0-2 0-i 慢慢增大区间
		newNumIndex := end
		for newNumIndex-1>=0 && arr[newNumIndex-1] > arr[newNumIndex] { // 在0-end区间内，从最后一个数开始与建一个数比较
			Swap(arr, newNumIndex, newNumIndex-1)
			newNumIndex--
		}
	}
}
